% multiple1902 <multiple1902@gmail.com>
% available on https://code.google.com/p/xjtu-cs-lect/
% licensed under cc by-sa 3.0
\chapter{排列与组合}

\section*{课前思考}

    \begin{enumerate}
        \item 2个互异的球放入3个互异的盒子, 每个盒子至多一个球, 有多少方案? 
        \item 2个互异的球放入3个互异的盒子, 每个盒子球数不限, 有多少方案? 
        \item 2个相同的球放入3个互异的盒子, 每个盒子至多一个球, 有多少方案? 
        \item 3个人围成一圈, 有多少方案? 
        \item 3颗不同的珠子串成一串项链, 有多少方案? 
        \item 5个人(每人都会开车)分乘2辆小轿车(每车4座), 有多少方案? 
    \end{enumerate}

\section{加法原理与乘法原理}

    \paragraph{加法原理}
        
        设事件$A_1$有$m_1$种产生方式, 事件$A_2$有$m_2$种产生方式, \ldots, 事件$A_n$有$m_n$种产生方式, 则事件$A_1$或$A_2$或$\ldots$或$A_n$之一有$m_1+m_2+\cdots+m_n$种产生方式.

        \subparagraph{集合论语言}

            若$|A_1|=m_1, |A_2|=m_2, \cdots, |A_n|=m_n$, 并且$A_i\cap A_j=\emptyset(1\leqslant i\neq j\leqslant n)$, 则$|A_1\cup A_2\cup\cdots\cup A_n|=m_1+m_2+\cdots+m_n$.

    \paragraph{乘法原理}

        设事件$A_1$有$m_1$种产生方式, 事件$A_2$有$m_2$种产生方式, \ldots, 事件$A_n$有$m_n$种产生方式, 则事件$A_1$与$A_2$与$\ldots$与$A_n$之一有$m_1\times m_2\times \cdots\times m_n$种产生方式.

        \subparagraph{集合论语言}

            若$|A_1|=m_1, |A_2|=m_2, \cdots, |A_n|=m_n$, 并且$A_1\times A_2\times \cdots \times A_n=\{(a_1,a_2,\cdots,a_n)|a_i\in A_i(1\leqslant i\leqslant n)\}$, 则$|A_1\times A_2\times\cdots\times A_n|=m_1+m_2+\cdots+m_n$.

        \begin{example}
            \begin{enumerate}
                \item 求小于10000的含1的正整数的个数(3439)
                \item 求小于10000的含0的正整数的个数(2619)
            \end{enumerate}
        \end{example}

\section{排列与组合}

    \subsection{无重排列}

        \begin{definition}[无重排列]
            从$n$个不同的元素中, 取$r$个不重复的元素, 按次序排成一列, 称为从$n$个元中取$r$个元的\textsf{(无重)排列}. 这些排列的全体组成的集合用$\mathbf{\P(n,r)}$表示. 排列的个数用$\P(n,r)$表示. 当$r=n$时, 称为\textsf{全排列}. 一个排列也可看作一个字符串, $r$也称为排列或字符串的长度. 
        \end{definition}

        \begin{caution}
            一般没说可重复意即无重复
        \end{caution}

        \begin{theorem}
            $\P(n,r)=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}$
        \end{theorem}

    \subsection{无重组合}

        \begin{definition}[无重组合]
            从$n$个不同元素中, 取$r$个不重复的元素, 不考虑其次序, 构成一个子集, 称为从$n$个元中取$r$个元的\textsf{(无重)组合}. 这些组合的全体组成的集合用$\mathbf{\C(n,r)}$表示, 组合的个数用$\C(n,r)$或$n\choose r$表示.
        \end{definition}
        \begin{theorem}
            $\C(n,r)=\frac{n!}{r!(n-r)!}$
        \end{theorem}

        \subparagraph{组合模型}

            组合的计数相当于将$r$个相同的球放入$n$个不同的盒子里, 每盒最多1个球的方案数.

        \begin{prop}
            ${n\choose r}={n\choose n-r}=\frac{n!}{r!(n-r)!}$, $\C^n_r=\C^{n-1}_r+\C^{n-1}_{r-1}$
        \end{prop}

    \subsection{可重排列}

        \begin{definition}[可重排列]
            从$n$个不同的元素中, 取$r$个可重复的元素, 按次序排成一列, 称为从$n$个元中取$r$个元的\textsf{可重排列}. 这些排列的全体组成的集合, 用$\mathbf{\overline{\P}(n,r)}$表示.  排列的个数用$\overline{\P}(n,r)$表示
        \end{definition}

        \begin{theorem}
            $\overline{\P}(n,r)=n^r$
        \end{theorem}

        \begin{definition}[多重排列]
            将$r_1$个$x_1$, $r_2$个$x_2$,\ldots, $r_k$个$x_k$按次序排成一列, 称为一个$(r_1,r_2,\cdots,r_k)$\textsf{多重排列}. 设$\sum_{i=1}^kr_i=n$, 这些排列的全体组成的集合, 表示为$\mathbf{\overline \P(n,x_1,x_2,\cdots,x_k)}$. 这些排列的个数用$n\choose{r_1,r_2,\cdots,r_k}$表示. 
        \end{definition}

        \begin{theorem}
            ${n\choose{r_1,r_2,\cdots,r_k}}=\frac{n!}{r_1!r_2!\cdots r_k!}$
        \end{theorem}

        \subparagraph{组合模型}

            $r_1$个$x_1$, $r_2$个$x_2$, \ldots, $r_k$个$x_k$排列的个数相当于$n$个不同的球放入$k$个不同的盒子里, 其中 $r_1$个球放入盒子$x_1$中, \ldots, $r_k$个球放入盒子$x_k$中的方案数(合子中的球不计次序). 

    \subsection{多项式系数}

        \begin{definition}[多项式系数]
            多项式的展开式是$n$次对称多项式:
            \[(x_1+x_2+\cdots+x_k)^n=\sum_{r_1+r_2+\ldots+r_k=n}\mathrm{C}_{r_1,r_2,\ldots,r_k}x_1^{r_1}x_2^{r_2}\cdots x_k^{r_k}\]
            此展开式中任意一项$\mathrm{C}_{r_1,r_2,\ldots,r_k}x_1^{r_1}x_2^{r_2}\cdots x_k^{r_k}$前面的$\mathrm{C}_{r_1,r_2,\ldots,r_k}$的值称为\textsf{多项式系数}.
        \end{definition}

        \begin{theorem}\rm
            $\mathrm{C}_{r_1,r_2,\ldots,r_k}={n\choose r_1,r_2,\ldots,r_k}$, 其中$\sum_{i=1}^kr_i=n$
        \end{theorem}

    \subsection{圆排列和项链排列}

        \begin{definition}[圆排列]
            如若将一个排列的首尾相连, 布列在一个圆周上, 则称其为一个\textsf{圆排列}. 若两个圆排列不离开平面, 通过\textbf{旋转}和\textbf{平移}就能够重合, 则看做是同一个圆排列. 由$r$个字符构成的圆排列可在$r$处做顺时针断开.
        \end{definition}

        \begin{definition}[项链排列]
            \textsf{项链排列}是圆排列. 一般而言, 若两个项链排列通过旋转, 平移和\textbf{翻转}就能够重合, 则看做是同一个项链排列. 
        \end{definition}

        \begin{theorem}\rm
            从$n$个字符中取$r$个不同的字符构成\textbf{圆排列}的个数为$Q^n_r=\P(n,r)/r$ ($0\leqslant r\leqslant n$).

            从$n$个字符中取$r$个不同的字符构成\textbf{项链排列}的个数为$\P(n,r)/2r$ ($3\leqslant r\leqslant n$).
        \end{theorem}

        关于可重的圆排列和项链排列, 我们将在讨论Mobius反演及P\`olya定理时涉及.

        \begin{example}
            从$[1,300]$中取3个不同的数, 使这3个数的和能被3整除, 有多少种方案? 

            \begin{sol}
                将[1,300]分成3类: 
                \begin{itemize}
                    \item $A={i|i\equiv1(\mathrm{mod\ }3)}={1,4,7,\cdots,298}$,
                    \item $B={i|i\equiv2(\mathrm{mod\ }3)}={2,5,8,\cdots,299}$,
                    \item $C={i|i\equiv3(\mathrm{mod\ }3)}={3,6,9,\cdots,300}$.
                \end{itemize}
                要满足条件, 有四种解法: 
                \begin{enumerate}
                    \item 3个数同属于$A$;
                    \item 3个数同属于$B$;
                    \item 3个数同属于$C$;
                    \item $A$, $B$, $C$各取一数.
                \end{enumerate}
                故共有$3\mathrm{C}(100,3)+100^3=485000+1000000=1485000$种方案.
            \end{sol}
        \end{example}

        \begin{example}
            某车站有6个入口处, 每个入口处每次只能进一人, 一组9个人进站的方案有多少? 

            \begin{sol}
                一进站方案表示成: 00011001010100. 其中``0''表示人, ``1''表示门框, 其中``0''是不同元, ``1''是相同元. $n$个门只用$n-1$个门框. 任意进站方案可表示成上面14个元素的一个排列. 
                \subparagraph{\rm\textbf{[解法1]}} 标号可产生$5!$个14个元的全排列. 故若设$x$为所求方案, 则$x\times5!=14!\therefore x=14!/5!=726485760$.
                \subparagraph{\rm\textbf{[解法2]}} 在14个元的排列中先确定``1''的位置, 有C$(14,5)$种选择, 再确定人的位置, 有$9!$种选择. 故C$(14,5)\times9!$即所求. 
                \subparagraph{\rm\textbf{[解法3]}} 把全部选择分解成若干步, 使每步宜于计算. 不妨设9个人编成1至9号. 1号有6种选择; 2号除可有1号的所有选择外, 还可(也必须)选择当与1号同一门时在1号的前面还是后面, 故2号有7种选择; 3号的选择方法同2号, 故共有8种. 以此类推, 9号有14种选择. 故所求方案数为$[6]^9$(上阶乘). 
            \end{sol}
        \end{example}

\section{Stirling近似公式}

    \textsf{Stirling公式}给出一个求$n!$的近似公式, 它对从事计算和理论分析都是有意义的. 

    \paragraph{Wallis公式}

        \[\lim_{n\to\infty}(\frac{2^{2n}(n!)^2}{(2n)!})^2\frac{1}{2n+1}=\frac{\pi}{2}\]

    \paragraph{Stirling公式}

        \[n!\sim\sqrt{2\pi n}({n\over \e})^n\]

\section{模型转换--一一对应技术}

    \textsf{一一对应}是组合数学基本方法中极为基本, 至为重要的概念和方法之一. 尤其是解决计数问题的基本概念和方法. 一一对应又称为\textsf{归约方法}. 归约思想乃是数学思想中很重要的一种思想. 

    \paragraph{一一对应(归约)}

        假设有A问题和B问题, 其中A问题解决的方案集就记为$A$集合, 方案个数为$|A|$,  B问题解决的方案集就记为$B$集合, 方案个数为$|B|$. 现在要求解的是A问题, 但是比较复杂, 难求, 或是新问题; 而B问题易求, 或已知其解. 若我们能将A问题一一对应的转化为B问题, 实际上是能在$A$集合和$B$集合之间建立一双射函数(映射)$f:A\to B$则我们就有$|A|=|B|$. 

    \paragraph{多对一}

        假设有A问题和B问题, 其中A问题解决的方案集就记为$A$集合, 方案个数为$|A|$,  B问题解决的方案集就记为$B$集合, 方案个数为$|B|$. 若我们能将多个A问题的方案对应的转化为一个B问题的方案, 实际上是在$A$集合和$B$集合之间建立一\textsf{多对一函数}(映射)$f:A\to B$使得每$l$个$A$的元素都对应一个$B$的元素($l$称为\textsf{重复系数}), 那么我们就有$|A|=l|B|$或$|B|=\frac{1}{l}|A|$.

    因此, 在组合计数及组合方案设计时, 往往借助于一一对应技术来实现模型转换. 比如要对$A$集合计数, 但直接计数有困难, 于是可设法构造一易于计数的$B$集合, 使得$A$与$B$一一对应. 

    \begin{theorem}[格路定理]\rm
        设$c\geqslant a, d\geqslant b$, 则由$(a,b)$到$(c,d)$的\textsf{简单格路数}为
        \[\left|(a,b)-(c,d)\right|={(c-a)+(d-b)\choose c-a}\]
    \end{theorem}

    \begin{example}
        设$m<n$, 求$(0,1)$点到$(m,n)$点不接触对角线$x=y$的格路的数目(``接触''包括``穿过''). 

        \begin{sol}
            从$(0,1)$点到$(m,n)$点的格路, 有的接触$x=y$, 有的不接触. 对每一条接触$x=y$的格路, 做$(0,1)$点到第一个接触点部分关于$x=y$的对称格路, 这样得到一条从$(1,0)$到$(m,n)$的格路. 容易看出从$(0,1)$到$(m,n)$接触$x=y$的格路与$(1,0)$到$(m,n)$的格路(必穿过$x=y$)一一对应. 故所求格路数为
            \begin{flalign*}
                &{m+n-1\choose m}-{m+n-1\choose m-1} \\
                =&\frac{(m+n-1)!}{m!(n-1)!}-\frac{(m+n-1)!}{(m-1)!n!} \\
                =&\frac{(m+n-1)!}{(m-1)!(n-1)!}\cdot\left( \frac 1m-\frac 1n \right) \\
                =&\frac{n-m}{n}{m+n-1\choose m}\\
                =&\left( 1-\frac mn \right){m+n-1\choose m}
            \end{flalign*}

            若条件改为可接触但不可穿过, 则限制线要向下或向右移一格, 得$x-y=1$, $(0,0)$关于$x-y=1$的对称点为$(1,-1)$, 所求格路数为
            \begin{flalign*}
                &{m+n\choose m}-{m+n\choose m-1} \\
                =&\frac{(m+n)!}{m!n!}-\frac{(m+n)!}{(m-1)!(n+1)!} \\
                =&\frac{n+1-m}{n+1}{m+n\choose m}
            \end{flalign*}
            \begin{note}
                此题所用方法为\textsf{反射法}:
                \begin{description}
                    \item[强领(优)先条件] $(a,b)$满足$b>a$
                    \item[弱领(优)先条件] $(a,b)$满足$b\geqslant a$
                \end{description}
            \end{note}
        \end{sol}
    \end{example}

    \begin{example}[树和序列]
        给定一棵有标号的树.

        \subparagraph{由树形成序列的过程}
            逐个摘去标号最小的叶子, 叶子的\textbf{相邻顶点}(不是叶子, 是内点)形成一个序列.

        \subparagraph{由序列形成树的过程}
        给定序列$b=(b_1, b_2,\cdots,b_{n-2})$, 设$a=(1,2,3,\cdots,n-1, n)$,将b的各位插入a,得$a'$,对$b'\choose a'$做操作. $a'$是$2n-2$个元的可重非减序列. 操作是从$a'$中去掉最小的无重元, 设为$a_1$, 再从$b$和$a'$中各去掉一个$b$中的第一个元素, 设为$b_1$, 则无序对$(a_1, b_1)$是一条边. 重复这一操作, 得$n-2$条边, 最后$a'$中还剩一条边, 共$n-1$条边, 正好构成一个树. $b$中每去掉一个元, $a'$中去掉2个元. 
    \end{example}

    \begin{theorem}[Cayley定理] \rm
        $n$个有标号$1,2,\cdots,n$的顶点的树的数目等于$n^{n-2}$.
    \end{theorem}
    该定理说明, 用$n-1$条边将$1,2,\cdots,n$点链接起来的连通图的数目为$n^{n-2}$.


\section{全排列的生成算法}

    本节讨论4种全排列的生成算法.

    \subsection{字典序法}

        \begin{definition}[字典序]
            设$(\Sigma,\leqslant)$是一全序集. 其中: $\Sigma$是一有限集, 称为\textsf{字母表}, 任一元素$a\in\Sigma$称为\textsf{字母}, $\leqslant$是字母表中字母的\textsf{自然顺序}, 则显然$\leqslant$是一个\textsf{全序}. 故此,则$(\Sigma^*,\leqslant^*)$是一\textsf{全序集},我们称其为\textsf{字典序}. 其中$\Sigma^*=\{\wedge\}\cup\Sigma\cup\Sigma^2\cup\Sigma^3\cup\cdots\cup\Sigma^n\cup\cdots$, $\wedge$称为空字, 其任何元素$w\in\Sigma^*$称为一个字, 必有$k\in\mathbb{N}$, 使得$w\in\Sigma^k$, 从而$w=(a_{i1},a_{i2},a_{i3},\cdots,a_{ik})=a_{i1}a_{i2}a_{i3}\cdots a_{ik}$, 这里$a_{ij}\in\Sigma$, $1\leqslant j\leqslant k$.
        \end{definition}

        \subsubsection{生成给定全排列的下一个排列}

            所谓一个的下一个就是这一个与下一个之间没有其它的. 这就要求这一个与下一个有尽可能长的共同前缀, 也即变化限制在尽可能短的后缀上. 
            
            \begin{algorithm}[在字典序中求一个排列的下一个排列]
                 一般而言, 设$P$是$[1,n]$的一个全排列. 
                 \begin{enumerate}
                     \item $P=P_1P_2\cdots P_n=P_1P_2\cdots P_{j-1}P_{j}P_{j+1}\cdots P_{k-1}P_kP_{k+1}\cdots P_n$, 这里$j=\max\{i|P_i<P_i+1\}, k=\max\{i|P_i>P_j\}$;
                     \item 对换$P_j$, $P_k$得到$Q'=P_1P_2\cdots P_{j-1}P_kP_{j+1}\cdots P_{k-1}P_jP_{k+1}\cdots P_n$;
                     \item 将$P_{j+1}\cdots P_{k-1}P_jP_{k+1}\cdots P_n$翻转得到$Q=P_1P_2\cdots P_{j-1}P_kP_n\cdots P_{k+1}P_jP_{k-1}\cdots P_{j+1}$.
                 \end{enumerate}
             \end{algorithm}

            \begin{example}
                求给定排列839647521的下一个排列(839651247)
            \end{example}

             \begin{definition}[字典序中中介数和序号]
                 \begin{enumerate}
                     \item 排列$P=P_1P_2\cdots P_n$的\textsf{中介数}为\\$(k_1,k_2,\cdots,k_{n-1})=k_1k_2\cdots k_{n-1}$, 这里$k_i$表示$P_i$的右边比$P_i$的数的个数$(1\leqslant i\leqslant n)$;
                     \item 排列$P=P_1P_2\cdots P_n$的\textsf{序号}可表示为
                         \begin{flalign*}
                             m&=m(P)=k_1(n-1)!+k_2(n-2)!+\cdots+k_{n-1}\cdot 1! \\
                              &=\sum_{i=1}^{n-1}k_i(n-i)!
                          \end{flalign*}
                \end{enumerate}
            \end{definition}

        \subsubsection{计算给定排列的序号}

            \begin{example}
                求给定排列839647521的序号,即先于此排列的排列的个数
            \end{example}

        \subsubsection{计算给定中介数的排列}

            \begin{example}
                求中介数为72642321的排列
            \end{example}

        \subsubsection{计算给定序号的中介数}

            \begin{example}
                求序号为297191的中介数(72642321)
            \end{example}
            
    \subsection{递增进位制数法}

        \begin{definition}[递增进位制数]
            设数$m$表示为$m=b_nb_{n-1}\cdots b_3b_2=b_n(n-1)!+b_{n-1}(n-2)!+\cdots+b_3\cdot2!+b_2\cdot1!$, 其中$0\leqslant b_i\leqslant i-1, 2\leqslant i\leqslant n$. 可以看出$m$是一$n-1$位的进位链, 右起第1位逢2进1, 右起第2位逢3进1, \ldots, 右起第$n-2$位逢$n-1$进1, 右起第$n-1$位逢$n$进1. 这样表示数的进位制我们称为\textsf{递增进位制数}(又称为递增进制或阶乘进制). 
        \end{definition}

        \begin{definition}[递增进制下的中介数和序号]
            \begin{enumerate}
                \item 排列$P=P_1P_2\cdots P_n$的\textsf{中介数}为\\$(a_n,a_{n-1},\cdots, a_3,a_2)=a_na_{n-1}\cdots a_3a_2$, 这里$a_i$表示$P$中数$i$的右边比$i$小的数的个数($1\leqslant i\leqslant n$);
                \item 排列$P=P_1P_2\cdots P_n$的\textsf{序号}可表示为递增进制
                    \begin{flalign*}
                        m&=m(P)=a_n(n-1)!+a_{n-1}(n-2)!+\cdots+a_3\cdot2!+a_2\cdot1! \\
                         &=\sum_{i-1}^{n-1}a_{i+1}\cdot i!
                    \end{flalign*}
            \end{enumerate}
        \end{definition}

        \subsubsection{由排列求中介数}

            \begin{example}
                求排列839647521的中介数(67342221)
            \end{example}

        \subsubsection{由中介数求排列}

            \begin{example}
                求中介数67342221的排列(839647521)
            \end{example}

        \subsubsection{由中介数求序号}

            \begin{example}
                求中介数67342221对应的序号(270095)
            \end{example}

        \subsubsection{由序号求中介数}

            \begin{algorithm}[在递增进制下由序号$m$求中介数$A$的算法]
                \begin{enumerate}
                    \item 令$n_1=m$;
                    \item $n_{i+1}=\lfloor\frac{n_i}{i+1}\rfloor$, $r_i=n_i-(i+1)n_{i+1}$, $i\leqslant i\leqslant n-1$;
                    \item 令$a_i=r_{i-1}$, $2\leqslant i\leqslant n$.
                \end{enumerate}
                中介数$A=a_na_{n-1}\cdots a_3a_2$.
            \end{algorithm}

            \begin{example}
                求序号为279905的中介数(67342221)
            \end{example}

        \subsubsection{根据中介数计算给定排列的下一个排列}

            \begin{example}
                求排列839647521的下一个排列(849617523)
            \end{example}

    \subsection{递减进位制数法}

        与字典序法相比, 递增进位制数法在从中介数恢复排列方面简便了许多. 但是用递增进位制数法直接生成下一个排列却不是很方便. 只有在1在2的左边时, 可以通过对换两个数字得到下一个排列. 在很多情况下, 需要改变许多数字的位置. 究其原因, 递增进位制数的进制从右向左依次增大, 右边进制小, 所以加1时很容易发生改变. 某位进位后该位由非零变为0, 导致这一位对应的数字在排列中的位置可能发生改变. 为了降低进位频率, 应使右边的进制大. 于是提出了递减进位制数法. 

        \begin{definition}
            [递减进位制数]
            设数$m$表示为
            \begin{flalign*}
                m&=b_2b_3\cdots b_{n-1}b_n \\
                 &=b_n\cdot 1+b_{n-1}\cdot n+b_{n-2}\cdot n(n-1)+\cdots+b_3\cdot n!/3!+b_2\cdot n!/2!
            \end{flalign*}
            其中$0\leqslant b_i\leqslant i-1, 2\leqslant i\leqslant n$. 可以看出$m$是一$n-1$位的进位链, 右起第1位逢$n$进1, 右起第2位逢$n-1$进1, \ldots, 右起第$n-2$位逢3进1, 右起第$n-1$位逢2进1. 这样表示数的进位制称为\textsf{递减进位制数}(又称为递减进制). 
        \end{definition}

        \begin{definition}
            [递减进制下的中介数和序号]
            \begin{enumerate}
                \item 排列$P=P_1P_2\cdots P_n$的\textsf{中介数}为\\$(a_2,a_3,\cdots,a_{n-1},a_n)=a_2a_3\cdots a_{n-1}$, 这里$a_i$是$P$中数$i$的右边比$i$小的数的个数;
                \item 排列$P=P_1P_2\cdots P_n$的\textsf{序号}可表示为递减进制
                    \begin{flalign*}
                        m&=m(P)=a_n\cdot1+a{n-1}\cdot n+a_{n-2}\cdot n(n-1)+\cdots+a_3\cdot n!/3!+a_2\cdot n!/2! \\
                         & n!\sum_{i=2}^na_i/i!
                    \end{flalign*}
            \end{enumerate}
        \end{definition}

        \subsubsection{根据中介数计算给定排列的下一个排列}

            \begin{example}
                求排列839647521的下一个排列(893647521)
            \end{example}

        \subsubsection{直接计算给定排列的下一个排列}

            \begin{example}
                求排列987635421的下一个排列(534216789)
            \end{example}

        \begin{algorithm}
            [在递减进制中求一个排列的下一个排列的算法]
            一般而言, 设$P=P_1P_2\cdots P_n$是$[1,n]$的一个全排列,
            \begin{enumerate}
                \item 当$P_1<n$时, 设$P_j=n$, 则交换$P_j$与$P_{j-1}$, 得到$Q=P_1P_2\cdots P_jP_{j-1}P_{j+1}\cdots P_n$;
                \item 当$P_1=n$时, 寻找$j$使得$P_i=n-i+1$, $i=1,2,\cdots,j-1$, 但$P_j<n-j+1$, 则将$P_1P_2\cdots P_j-1$翻转为$P_{j-1}\cdots P_2P_1$, 并置于$P_n$之后, 得$Q'=P_jP_{j+1}\cdots P_nP_{j-1}\cdots P_2P_1$;
                \item 再设$P_k=n-j+1$, 则交换$P_k$与$P_{k-1}$, 于是得$Q=P_jP_{j+1}\cdots P_kP_{k-1}P_{k+1}\cdots P_nP_{j-1}\cdots P_2P_1$.
            \end{enumerate}
        \end{algorithm}
    
    \subsection{邻位对换法}

        递减进位制数法的中介数进位不频繁, 求下一个排列在不进位的情况下很容易. 这就启发我们设计一种算法, 下一个排列总是上一个排列某相邻两位对换得到的. 递减进位制数字的换位是单向的, 从右向左, 而邻位对换法的换位是双向的. 
    
        \begin{definition}
            [逆序与逆序数, 奇排列与偶排列]
            \begin{enumerate}
                \item 排列$P=P_1P_2\cdots P_n$中, 若$i<j\Rightarrow P_i>P_j$, 则称$P_i$与$P_j$构成一对\textsf{逆序}, 排列中所有逆序的对数称为排列$P$的\textsf{逆序数};
                \item 若排列$P_1P_2\cdots P_n$的逆序数是奇数, 则称排列$P$为\textsf{奇排列}; 若是偶数, 则称排列$P$为\textsf{偶排列}. 
                \item 令$s_i$为$P_i$的右面比$P_i$小的数字的个数, 其中$i=1,2,\cdots,n-1)$, 则排列$P$的逆序数为$S=\sum_{i=1}^{n-1}s_i$.
            \end{enumerate}
        \end{definition}

        \begin{definition}
            [邻位对换法中数$k$上箭头的方向]
             排列$P=P_1P_2\cdots P_n$中数$k$上的箭头方向, 由排列$P$中$1---k-1$所构成的排列的奇偶性决定, 当其为偶时, 箭头向左, 当其为奇时, 箭头向右, $k=2,3,\cdots,n$. 数2上的箭头规定向左. 
        \end{definition}

        \begin{example}
            确定排列839647521中各数上的箭头方向

            \begin{sol}
                2上箭头向左: 因1是偶排列(逆序数为0); \\
                3上箭头向右: 因21是奇排列(逆序数为1); \\
                4上箭头向右: 因321是奇排列(逆序数为3); \\
                5上箭头向右: 因3421是奇排列(逆序数为5); \\
                6上箭头向右: 因34521是奇排列(逆序数为7); \\
                7上箭头向右: 因364521是奇排列(逆序数为11); \\
                8上箭头向左: 因3647521是偶排列(逆序数为14); \\
                9上箭头向右: 因83647521是奇排列(逆序数为21);\\
            \end{sol}
        \end{example}

        \begin{definition}
            [邻位对换法的中介数和序号]
            \begin{enumerate}
                \item 排列$P=P_1P_2\cdots P_n$的\textsf{中介数}为\\$(b_2,b_3,\cdots,b_{n-1},b_n)=b_2b_3\cdots b_{n-1}b_n$, 这里$b_i$: 对于$P$中数$i$, 当$i$上的箭头向右时, 则是$i$的左边比$i$小的数的个数$(1\leqslant i\leqslant n)$; 当$i$上的箭头向左时, 则是$i$的右边比$i$小的数的个数$(1\leqslant i\leqslant n)$. 
                \item 排列$P=P_1P_2\cdots P_n$的\textsf{序号}可表示为递减进制
                    \begin{flalign*}
                        m&=m(P)=b_n\cdot1+b_{n-1}\cdot n+b_{n-2}\cdot n(n-1)+\cdots+b_3\cdot n!/3!+b_2\cdot n!/2! \\
                         &=n!\cdot\sum_{i=2}^{n}b_i/i!
                    \end{flalign*}
            \end{enumerate}
        \end{definition}

        \begin{algorithm}
            [邻位对换法求一个排列的下一个排列]
            一般而言, 设$P=P_1P_2\cdots P_{j-1}P_jP_{j+1}\cdots P_n$是$[1,n]$的一个长度为$n$的全排列, 其中$P_j=n$, $1\leqslant j\leqslant n$
            \begin{enumerate}
                \item 当$P'=P_1P_2\cdots P_{j-1}P_{j+1}\cdots P_n$是$1$---$n-1$的一个偶排列时,
                    \begin{enumerate}
                        \item 当$j>1$时(即, $n$不在$P$的开头), $n$从右到左插入该排列$n-1$个字符的$n$个空档(包括两端), 生成$1$---$n$的$n$个排列. 因此, 排列$P$的下一个排列$Q=P_1P_2\cdot P_jP_{j-1}P_{j+1}\cdot P_n$;
                        \item 当$j=1$时(即, $n$在$P$的开头), 则对长度为$n-1$的排列$P'=P_2P_3\cdot P_n$递归地调用本算法, 求得$P'$的下一个长度为$n-1$的排列$Q'$. 不妨设$Q'=Q_1Q_2\cdots Q_{n-1}$, 则排列$P$的下一个排列$Q=P_1Q_1Q_2\cdots Q_{n-1}$. 
                    \end{enumerate}
                \item 当$P'=P_1P_2\cdots P_{j-1}P_{j+1}\cdots P_n$是1---$n-1$的一个奇排列时
                    \begin{enumerate}
                        \item 当$j<n$时(即, $n$不在$P$的尾部),  $n$从左到右插入该排列$n-1$个字符的$n$个空档(包括两端), 生成1---$n$的$n$个排列. 因此, 排列$P$的下一个排列$Q=P_1P_2\cdots P_{j-1}P_{j+1}P_j\cdots P_n$. 
                        \item 当$j=n$时(即, $n$在$P$的尾部), 则对长度为$n-1$的排列$P'=P_1P_2\cdots P_{n-1}$递归地调用本算法, 求得$P'$的下一个长度为$n-1$的排列$Q'$. 不妨设$Q'=Q_1Q_2\cdots Q_{n-1}$, 则排列$P$的下一个排列$Q=Q_1Q_2\ldots Q_{n-2}Q_{n-1}P_n$. 
                    \end{enumerate}
            \end{enumerate}
        \end{algorithm}

        \begin{example}
            由给定的中介数$(10121372)\downarrow$求其对应排列的序号. 

            \begin{sol}
                \begin{flalign*}
                    m&=1\cdot 9!/2!+0\cdot 9!/3!+1\cdot 9!/4!+2\cdot 9!/5!+1\cdot 9!/6!+3\cdot 9!/7!+7\cdot 9!/8!+2\cdot 9!/9! \\
                     &=\left(\left(\left(\left(\left(\left(1\cdot 3+0\right)\cdot 4+1\right)\cdot 5+2\right)\cdot 6+1\right)\cdot 7+3\right)\cdot 8+7\right)\cdot 9+2 \\
                     &=203393
                \end{flalign*}
            \end{sol}
        \end{example}

        \begin{example}
            求长度为9的全排列836475219的下一个排列.
        \end{example}

        \begin{example}
            求长度为9的全排列839647521的下一个排列及其中介数(10121372). 
        \end{example}
    
\section{组合的生成}

    \begin{algorithm}
        [求一个组合的下一个组合的算法]
        从$[1,n]$中取$r$个元的组合全体是$\C(n,r)$. 设$\C=c_1c_2\cdots c_r\in\C(n,r)$是一元的组合. 不妨设$c_1<c_2<\cdots<c_r$, $i\leqslant c_i\leqslant(n-r+i)$, $i=1,2,\leqslant,r$. 令$j=\max\{i|c_i<n-r+i\}$, 则$c_1c_2\cdots c_r$的下一个组合为$C'=c_1c_2\cdots c_{j-1}(c_j+1)(c_j+2)\cdots(c_j+r-j+1)$.
        \begin{note}
            这等于给$\C(n,r)$的元素建立了字典序.
        \end{note}
    \end{algorithm}

    \begin{example}
        用两种方法计算$[1,n]$的无重不相邻组合$C'(n,r)$的计数问题.

        $C'(n,r)={n-r\choose r-1}+{n-r\choose r}={n-r+1\choose r}$
    \end{example}

\section{可重组合}

    如果一个组合里的元素允许重复出现, 应当怎样计数呢?

    \subparagraph{思考题}
        从a,b,c这3个元素中取2个元素的可重复的组合有多少个? (${4\choose2}=6$)

    \begin{definition}
        [可重组合]
        从$n$个不同的元素中取$r$个可重复的元素, 称为从$n$个元中取$r$个元的\textsf{可重组合}. 这些组合的全体组成的集合用$\mathbf{\overline{C}(n,r)}$表示. 可重组合的个数用$\overline \C(n,r)$表示. 为了方便起见, 上述$n$个不同的元素就取$[1,n]$中的整数. 
    \end{definition}

    \begin{theorem}
        $\overline \C(n,r)={n+r-1\choose r}$
    \end{theorem}

\section{若干等式及其组合意义}

    \begin{enumerate}
        \item $\C^n_r=\C^n_{n-r}$
        \item ${n\choose k}=\frac nk{n-1\choose k-1}$
        \item ${n\choose k}=\frac{n-k+1}k{n\choose k-1}$
        \item ${n\choose k}=\frac n{n-k}{n-1\choose k}$
        \item $\C^n_r=\C^{n-1}_r+\C^{n-1}_{r-1}$
        \item ${n\choose n}+{n+1\choose n}+{n+2\choose n}+\cdots+{n+r\choose n}={n+r+1\choose n+1}$
        \item ${n\choose l}{l\choose r}={n\choose r}{n-l\choose l-r}$
        \item ${m\choose0}+{m\choose 1}+\cdots+{m\choose m}=2^m, m\geqslant0$
        \item ${n\choose0}-{n\choose1}+{n\choose2}-\cdots+(-1)^n{n\choose n}=0$
        \item ${m+n\choose r}={m\choose0}{n\choose r}+{m\choose1}{n\choose r-1}+\cdots+{m\choose r}{n\choose 0}$ Vandermonde恒等式 \\
        $\sum_{j\geqslant0}{k\choose j}{l\choose j}{n+k+l-j\choose k+l}={n+k\choose k}{n+l\choose l}$ 李善兰恒等式
        \item ${m+n\choose m}={m\choose0}{n\choose0}+{m\choose1}{n\choose1}+\cdots+{m\choose m}{n\choose m}$
        \item $\P(n,r)=n\P(n-1,r-1)$
        \item $\P(n,r)=\P(n-1,r)+r\P(n-1,r-1)$
    \end{enumerate}
